{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are a number of functions in `itertools` that are concerned with thing like permutations and combinations.\n",
    "\n",
    "Let's look at each one briefly - I am not going to go into much depth as to what permutations and combinations are though - this is not meant to be a statistics course :-)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import itertools"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Cartesian Product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The cartesian product is actually a lot more useful than it might appear at first.\n",
    "\n",
    "Consider this example, where we want to create a multiplication table as we have seen before:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def matrix(n):\n",
    "    for i in range(1, n+1):\n",
    "        for j in range(1, n+1):\n",
    "            yield f'{i} x {j} = {i*j}'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can look at a few elements using `islice`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['2 x 1 = 2',\n",
       " '2 x 2 = 4',\n",
       " '2 x 3 = 6',\n",
       " '2 x 4 = 8',\n",
       " '2 x 5 = 10',\n",
       " '2 x 6 = 12',\n",
       " '2 x 7 = 14',\n",
       " '2 x 8 = 16',\n",
       " '2 x 9 = 18',\n",
       " '2 x 10 = 20']"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(itertools.islice(matrix(10), 10, 20))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that we iterated through the same sets (the numbers from 1 to 10) in a nested fashion.\n",
    "\n",
    "If we think of those two sets as \n",
    "$$\n",
    "s1 = \\{1, 2, 3, ..., 10\\}\n",
    "$$\n",
    "$$\n",
    "s2 = \\{1, 2, 3, ..., 10\\}\n",
    "$$\n",
    "then the Cartesian product of the two sets is:\n",
    "$$\n",
    "s_1 \\times s_2 = \\{(x_1, x_2) \\, \\vert \\, x_1 \\in s_1 \\, \\textrm{and} \\, x_2 \\in s_2\\}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another way to think of it is by creating a table (just like our multiplication table!):\n",
    "\n",
    "```\n",
    "        y1        y2        y3\n",
    "x1  (x1, y1)  (x1, y2)  (x1, y3)\n",
    "\n",
    "x2  (x2, y1)  (x2, y2)  (x2, y3)\n",
    "\n",
    "x3  (x3, y1)  (x3, y2)  (x3, y3)\n",
    "\n",
    "x4  (x4, y1)  (x4, y2)  (x4, y3)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our multiplication table was just the product of $x_i$ and $y_i$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "       y1       y2       y3      y4\n",
    "x1  x1 * y1  x1 * y2  x1 * y3  x1 * y4\n",
    "\n",
    "x2  x2 * y1  x2 * y2  x2 * y3  x2 * y4  \n",
    "\n",
    "x3  x3 * y1  x3 * y2  x3 * y3  x3 * y4  \n",
    "\n",
    "x4  x4 * y1  x4 * y2  x4 * y3  x4 * y4  \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, the Cartesian product of two iterables in general can be generated using a nested loop:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('x1', 'y1') ('x1', 'y2') ('x1', 'y3') \n",
      "('x2', 'y1') ('x2', 'y2') ('x2', 'y3') \n",
      "('x3', 'y1') ('x3', 'y2') ('x3', 'y3') \n",
      "('x4', 'y1') ('x4', 'y2') ('x4', 'y3') \n"
     ]
    }
   ],
   "source": [
    "l1 = ['x1', 'x2', 'x3', 'x4']\n",
    "l2 = ['y1', 'y2', 'y3']\n",
    "for x in l1:\n",
    "    for y in l2:\n",
    "        print((x, y), end=' ')\n",
    "    print('')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can achieve the same result with the `product` function in `itertools`. As usual, it is lazy as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('x1', 'y1'),\n",
       " ('x1', 'y2'),\n",
       " ('x1', 'y3'),\n",
       " ('x2', 'y1'),\n",
       " ('x2', 'y2'),\n",
       " ('x2', 'y3'),\n",
       " ('x3', 'y1'),\n",
       " ('x3', 'y2'),\n",
       " ('x3', 'y3'),\n",
       " ('x4', 'y1'),\n",
       " ('x4', 'y2'),\n",
       " ('x4', 'y3')]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l1 = ['x1', 'x2', 'x3', 'x4']\n",
    "l2 = ['y1', 'y2', 'y3']\n",
    "list(itertools.product(l1, l2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a simple example, let's go back to the multiplication table we created using a generator function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def matrix(n):\n",
    "    for i in range(1, n+1):\n",
    "        for j in range(1, n+1):\n",
    "            yield (i, j, i*j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 1, 1),\n",
       " (1, 2, 2),\n",
       " (1, 3, 3),\n",
       " (1, 4, 4),\n",
       " (2, 1, 2),\n",
       " (2, 2, 4),\n",
       " (2, 3, 6),\n",
       " (2, 4, 8),\n",
       " (3, 1, 3),\n",
       " (3, 2, 6),\n",
       " (3, 3, 9),\n",
       " (3, 4, 12),\n",
       " (4, 1, 4),\n",
       " (4, 2, 8),\n",
       " (4, 3, 12),\n",
       " (4, 4, 16)]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(matrix(4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def matrix(n):\n",
    "    for i, j in itertools.product(range(1, n+1), range(1, n+1)):\n",
    "        yield (i, j, i*j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 1, 1),\n",
       " (1, 2, 2),\n",
       " (1, 3, 3),\n",
       " (1, 4, 4),\n",
       " (2, 1, 2),\n",
       " (2, 2, 4),\n",
       " (2, 3, 6),\n",
       " (2, 4, 8),\n",
       " (3, 1, 3),\n",
       " (3, 2, 6),\n",
       " (3, 3, 9),\n",
       " (3, 4, 12),\n",
       " (4, 1, 4),\n",
       " (4, 2, 8),\n",
       " (4, 3, 12),\n",
       " (4, 4, 16)]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(matrix(4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And of course this is now simple enough to even use just a generator expression:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def matrix(n):\n",
    "    return ((i, j, i*j) \n",
    "            for i, j in itertools.product(range(1, n+1), range(1, n+1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 1, 1),\n",
       " (1, 2, 2),\n",
       " (1, 3, 3),\n",
       " (1, 4, 4),\n",
       " (2, 1, 2),\n",
       " (2, 2, 4),\n",
       " (2, 3, 6),\n",
       " (2, 4, 8),\n",
       " (3, 1, 3),\n",
       " (3, 2, 6),\n",
       " (3, 3, 9),\n",
       " (3, 4, 12),\n",
       " (4, 1, 4),\n",
       " (4, 2, 8),\n",
       " (4, 3, 12),\n",
       " (4, 4, 16)]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(matrix(4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You'll notice how we repeated the `range(1, n+1)` twice?\n",
    "\n",
    "This is a great example of where `tee` can be useful:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from itertools import tee\n",
    "\n",
    "def matrix(n):\n",
    "    return ((i, j, i*j) \n",
    "            for i, j in itertools.product(*itertools.tee(range(1, n+1), 2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 1, 1),\n",
       " (1, 2, 2),\n",
       " (1, 3, 3),\n",
       " (1, 4, 4),\n",
       " (2, 1, 2),\n",
       " (2, 2, 4),\n",
       " (2, 3, 6),\n",
       " (2, 4, 8),\n",
       " (3, 1, 3),\n",
       " (3, 2, 6),\n",
       " (3, 3, 9),\n",
       " (3, 4, 12),\n",
       " (4, 1, 4),\n",
       " (4, 2, 8),\n",
       " (4, 3, 12),\n",
       " (4, 4, 16)]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(matrix(4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A common usage of Cartesian products might be to generate a grid of coordinates.\n",
    "\n",
    "For a 2D space for example, we might want to generate a grid of points ranging from -5 to 5 in both the x and y axes, with a step of 0.5.\n",
    "\n",
    "We can't use a range since ranges need integral numbers, but we have the `count` function in itertools we have seen before:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def grid(min_val, max_val, step, *, num_dimensions=2):\n",
    "    axis = itertools.takewhile(lambda x: x <= max_val,\n",
    "                               itertools.count(min_val, step))\n",
    "    \n",
    "    # to handle multiple dimensions, we just need to repeat the axis that\n",
    "    # many times - tee is perfect for that\n",
    "    axes = itertools.tee(axis, num_dimensions)\n",
    "\n",
    "    # and now we just need the product of all these iterables\n",
    "    return itertools.product(*axes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(-1, -1),\n",
       " (-1, -0.5),\n",
       " (-1, 0.0),\n",
       " (-1, 0.5),\n",
       " (-1, 1.0),\n",
       " (-0.5, -1),\n",
       " (-0.5, -0.5),\n",
       " (-0.5, 0.0),\n",
       " (-0.5, 0.5),\n",
       " (-0.5, 1.0),\n",
       " (0.0, -1),\n",
       " (0.0, -0.5),\n",
       " (0.0, 0.0),\n",
       " (0.0, 0.5),\n",
       " (0.0, 1.0),\n",
       " (0.5, -1),\n",
       " (0.5, -0.5),\n",
       " (0.5, 0.0),\n",
       " (0.5, 0.5),\n",
       " (0.5, 1.0),\n",
       " (1.0, -1),\n",
       " (1.0, -0.5),\n",
       " (1.0, 0.0),\n",
       " (1.0, 0.5),\n",
       " (1.0, 1.0)]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(grid(-1, 1, 0.5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And of course we can now do it in 3D as well:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(-1, -1, -1),\n",
       " (-1, -1, -0.5),\n",
       " (-1, -1, 0.0),\n",
       " (-1, -1, 0.5),\n",
       " (-1, -1, 1.0),\n",
       " (-1, -0.5, -1),\n",
       " (-1, -0.5, -0.5),\n",
       " (-1, -0.5, 0.0),\n",
       " (-1, -0.5, 0.5),\n",
       " (-1, -0.5, 1.0),\n",
       " (-1, 0.0, -1),\n",
       " (-1, 0.0, -0.5),\n",
       " (-1, 0.0, 0.0),\n",
       " (-1, 0.0, 0.5),\n",
       " (-1, 0.0, 1.0),\n",
       " (-1, 0.5, -1),\n",
       " (-1, 0.5, -0.5),\n",
       " (-1, 0.5, 0.0),\n",
       " (-1, 0.5, 0.5),\n",
       " (-1, 0.5, 1.0),\n",
       " (-1, 1.0, -1),\n",
       " (-1, 1.0, -0.5),\n",
       " (-1, 1.0, 0.0),\n",
       " (-1, 1.0, 0.5),\n",
       " (-1, 1.0, 1.0),\n",
       " (-0.5, -1, -1),\n",
       " (-0.5, -1, -0.5),\n",
       " (-0.5, -1, 0.0),\n",
       " (-0.5, -1, 0.5),\n",
       " (-0.5, -1, 1.0),\n",
       " (-0.5, -0.5, -1),\n",
       " (-0.5, -0.5, -0.5),\n",
       " (-0.5, -0.5, 0.0),\n",
       " (-0.5, -0.5, 0.5),\n",
       " (-0.5, -0.5, 1.0),\n",
       " (-0.5, 0.0, -1),\n",
       " (-0.5, 0.0, -0.5),\n",
       " (-0.5, 0.0, 0.0),\n",
       " (-0.5, 0.0, 0.5),\n",
       " (-0.5, 0.0, 1.0),\n",
       " (-0.5, 0.5, -1),\n",
       " (-0.5, 0.5, -0.5),\n",
       " (-0.5, 0.5, 0.0),\n",
       " (-0.5, 0.5, 0.5),\n",
       " (-0.5, 0.5, 1.0),\n",
       " (-0.5, 1.0, -1),\n",
       " (-0.5, 1.0, -0.5),\n",
       " (-0.5, 1.0, 0.0),\n",
       " (-0.5, 1.0, 0.5),\n",
       " (-0.5, 1.0, 1.0),\n",
       " (0.0, -1, -1),\n",
       " (0.0, -1, -0.5),\n",
       " (0.0, -1, 0.0),\n",
       " (0.0, -1, 0.5),\n",
       " (0.0, -1, 1.0),\n",
       " (0.0, -0.5, -1),\n",
       " (0.0, -0.5, -0.5),\n",
       " (0.0, -0.5, 0.0),\n",
       " (0.0, -0.5, 0.5),\n",
       " (0.0, -0.5, 1.0),\n",
       " (0.0, 0.0, -1),\n",
       " (0.0, 0.0, -0.5),\n",
       " (0.0, 0.0, 0.0),\n",
       " (0.0, 0.0, 0.5),\n",
       " (0.0, 0.0, 1.0),\n",
       " (0.0, 0.5, -1),\n",
       " (0.0, 0.5, -0.5),\n",
       " (0.0, 0.5, 0.0),\n",
       " (0.0, 0.5, 0.5),\n",
       " (0.0, 0.5, 1.0),\n",
       " (0.0, 1.0, -1),\n",
       " (0.0, 1.0, -0.5),\n",
       " (0.0, 1.0, 0.0),\n",
       " (0.0, 1.0, 0.5),\n",
       " (0.0, 1.0, 1.0),\n",
       " (0.5, -1, -1),\n",
       " (0.5, -1, -0.5),\n",
       " (0.5, -1, 0.0),\n",
       " (0.5, -1, 0.5),\n",
       " (0.5, -1, 1.0),\n",
       " (0.5, -0.5, -1),\n",
       " (0.5, -0.5, -0.5),\n",
       " (0.5, -0.5, 0.0),\n",
       " (0.5, -0.5, 0.5),\n",
       " (0.5, -0.5, 1.0),\n",
       " (0.5, 0.0, -1),\n",
       " (0.5, 0.0, -0.5),\n",
       " (0.5, 0.0, 0.0),\n",
       " (0.5, 0.0, 0.5),\n",
       " (0.5, 0.0, 1.0),\n",
       " (0.5, 0.5, -1),\n",
       " (0.5, 0.5, -0.5),\n",
       " (0.5, 0.5, 0.0),\n",
       " (0.5, 0.5, 0.5),\n",
       " (0.5, 0.5, 1.0),\n",
       " (0.5, 1.0, -1),\n",
       " (0.5, 1.0, -0.5),\n",
       " (0.5, 1.0, 0.0),\n",
       " (0.5, 1.0, 0.5),\n",
       " (0.5, 1.0, 1.0),\n",
       " (1.0, -1, -1),\n",
       " (1.0, -1, -0.5),\n",
       " (1.0, -1, 0.0),\n",
       " (1.0, -1, 0.5),\n",
       " (1.0, -1, 1.0),\n",
       " (1.0, -0.5, -1),\n",
       " (1.0, -0.5, -0.5),\n",
       " (1.0, -0.5, 0.0),\n",
       " (1.0, -0.5, 0.5),\n",
       " (1.0, -0.5, 1.0),\n",
       " (1.0, 0.0, -1),\n",
       " (1.0, 0.0, -0.5),\n",
       " (1.0, 0.0, 0.0),\n",
       " (1.0, 0.0, 0.5),\n",
       " (1.0, 0.0, 1.0),\n",
       " (1.0, 0.5, -1),\n",
       " (1.0, 0.5, -0.5),\n",
       " (1.0, 0.5, 0.0),\n",
       " (1.0, 0.5, 0.5),\n",
       " (1.0, 0.5, 1.0),\n",
       " (1.0, 1.0, -1),\n",
       " (1.0, 1.0, -0.5),\n",
       " (1.0, 1.0, 0.0),\n",
       " (1.0, 1.0, 0.5),\n",
       " (1.0, 1.0, 1.0)]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(grid(-1, 1, 0.5, num_dimensions=3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another simple application of this might be to determine the odds of rolling an 8 with a pair of dice (with values 1 - 6).\n",
    "\n",
    "We can brute force this by generating all the possible results (the sample space), and counting how may items add up to 8.\n",
    "\n",
    "Let's break it up into a few steps:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]\n"
     ]
    }
   ],
   "source": [
    "sample_space = list(itertools.product(range(1, 7), range(1, 7)))\n",
    "print(sample_space)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we want to filter out the tuples whose elements add up to 8:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(2, 6), (3, 5), (4, 4), (5, 3), (6, 2)]\n"
     ]
    }
   ],
   "source": [
    "outcomes = list(filter(lambda x: x[0] + x[1] == 8, sample_space))\n",
    "print(outcomes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And we can calculate the odds by dividing the number acceptable outcomes by the size of the sample space. I'll actually use a `Fraction` so we retain our result as a rational number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5/36\n"
     ]
    }
   ],
   "source": [
    "from fractions import Fraction\n",
    "odds = Fraction(len(outcomes), len(sample_space))\n",
    "print(odds)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Permutations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From Wikipedia: \n",
    "\n",
    "\n",
    "> In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. These differ from combinations, which are selections of some members of a set where order is disregarded.\n",
    "\n",
    "\n",
    "https://en.wikipedia.org/wiki/Permutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can create permutations of length n from an iterable of length m (n <= m) using the `permutation` function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('a', 'b', 'c'),\n",
       " ('a', 'c', 'b'),\n",
       " ('b', 'a', 'c'),\n",
       " ('b', 'c', 'a'),\n",
       " ('c', 'a', 'b'),\n",
       " ('c', 'b', 'a')]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l1 = 'abc'\n",
    "list(itertools.permutations(l1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see all the permutations are, by default, the same length as the original iterable.\n",
    "\n",
    "We can create permutations of smaller length by specifying the `r` value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(itertools.permutations(l1, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The important thing to note is that elements are not 'repeated' in the permutation. The uniqueness of an element is **not** based on its value, but rather on its **position** in the original iterable.\n",
    "\n",
    "Take this example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('a', 'a', 'a'),\n",
       " ('a', 'a', 'a'),\n",
       " ('a', 'a', 'a'),\n",
       " ('a', 'a', 'a'),\n",
       " ('a', 'a', 'a'),\n",
       " ('a', 'a', 'a')]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(itertools.permutations('aaa'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This means that the following will yield what looks like the same permutations when considering the **values** of the iterable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('a', 'b'), ('a', 'a'), ('b', 'a'), ('b', 'a'), ('a', 'a'), ('a', 'b')]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(itertools.permutations('aba', 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, each tuple looks like it has been repeated twice - but considering the elements are unique based on their position, this is actually quite correct."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Combinations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From Wikipedia:\n",
    ">Combinations refer to the combination of n things taken k at a time without repetition. To refer to combinations in which repetition is allowed, the terms k-selection,[1] k-multiset,[2] or k-combination with repetition are often used.\n",
    "\n",
    "https://en.wikipedia.org/wiki/Combination"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`itertools` offers both flavors - with and without replacement.\n",
    "\n",
    "Let's look at a simple example with replacement first:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(itertools.combinations([1, 2, 3, 4], 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see `(4, 3)` is not included in the result since, as a combination, it is the same as `(3, 4)` - order is not important."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we want replacement:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 1),\n",
       " (1, 2),\n",
       " (1, 3),\n",
       " (1, 4),\n",
       " (2, 2),\n",
       " (2, 3),\n",
       " (2, 4),\n",
       " (3, 3),\n",
       " (3, 4),\n",
       " (4, 4)]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(itertools.combinations_with_replacement([1, 2, 3, 4], 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A simple application of this might be to calculate the odds of pulling four consecutive aces from a deck of 52 cards.\n",
    "\n",
    "That's very easy to figure out, but we could use a brute force approach by calculating all the 4-combinations (without repetition) from a deck of 52 cards.\n",
    "\n",
    "Let's try it:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we need a deck:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "SUITS = 'SHDC'\n",
    "RANKS = tuple(map(str, range(2, 11))) + tuple('JQKA')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K', 'A')"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "RANKS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I wanted all the elements in my `RANKS` to be strings - just to have a consistent data type, and to show you how handy `map` can be!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next I need to create the deck:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "deck = [rank + suit for suit in SUITS for rank in RANKS]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['2S', '3S', '4S', '5S', '6S']"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deck[0:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hmm... A nested loop. Maybe `product` would work well here!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "deck = [rank + suit for suit, rank in itertools.product(SUITS, RANKS)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I would much prefer having a named tuple for the deck, so let's do that as well:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import namedtuple\n",
    "Card = namedtuple('Card', 'rank suit')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "deck = [Card(rank, suit) for suit, rank in itertools.product(SUITS, RANKS)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And I really don't need it as a list - a generator expression will do just as well..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "deck = (Card(rank, suit) for suit, rank in itertools.product(SUITS, RANKS))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we need to produce our sample space - all combinations of 4 cards from the deck, without repetition:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sample_space = itertools.combinations(deck, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we need to count the number of acceptable outcomes - but we also need to count the size of our sample space.\n",
    "We can't use `len()` though - iterables in general don't support that method. \n",
    "I could create the sample space twice, but that seems wasteful - so instead I'm going to iterate through the sample space once and just keep track of both counts:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "total=270725, acceptable=1\n",
      "odds=1/270725\n",
      "odds=0.0000036938\n"
     ]
    }
   ],
   "source": [
    "deck = (Card(rank, suit) for suit, rank in itertools.product(SUITS, RANKS))\n",
    "sample_space = itertools.combinations(deck, 4)\n",
    "total = 0\n",
    "acceptable = 0\n",
    "for outcome in sample_space:\n",
    "    total += 1\n",
    "    for card in outcome:\n",
    "        if card.rank != 'A':\n",
    "            break\n",
    "    else:\n",
    "        # else block is executed if loop terminated without a break\n",
    "        acceptable += 1\n",
    "print(f'total={total}, acceptable={acceptable}')\n",
    "print('odds={}'.format(Fraction(acceptable, total)))\n",
    "print('odds={:.10f}'.format(acceptable/total))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can easily verify that this is correct:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Odds of succesively picking four aces from a shuffled deck is:\n",
    "\n",
    "$$\n",
    "\\frac{4}{52} \\times \\frac{3}{51} \\times \\frac{2}{50} \\times \\frac{1}{49}\n",
    "= \\frac{24}{6497400} = \\frac{1}{270725}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I also want to point out that we could use the `all` function instead of that inner `for` loop and the `else` block.\n",
    "\n",
    "Remember that `all(iterable)` will evaluate to True if all the elements of the iterable are truthy.\n",
    "Now in our case, since ranks are non-empty strings, they will always be truthy, so we can't use `all` directly:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all(['A', 'A', '10', 'J'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead we can use the `map` function, yet again!, to test if the value is an 'A' or not:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[False, True, True, True]\n",
      "[True, True, True, True]\n"
     ]
    }
   ],
   "source": [
    "l1 = ['K', 'A', 'A', 'A']\n",
    "l2 = ['A', 'A', 'A', 'A']\n",
    "\n",
    "print(list(map(lambda x: x == 'A', l1)))\n",
    "print(list(map(lambda x: x == 'A', l2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So now we can use `all` (and we don't have to create a list):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(all(map(lambda x: x == 'A', l1)))\n",
    "print(all(map(lambda x: x == 'A', l2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, we could rewrite our algorithm as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "total=270725, acceptable=1\n",
      "odds=1/270725\n",
      "odds=0.0000036938\n"
     ]
    }
   ],
   "source": [
    "deck = (Card(rank, suit) for suit, rank in itertools.product(SUITS, RANKS))\n",
    "sample_space = itertools.combinations(deck, 4)\n",
    "total = 0\n",
    "acceptable = 0\n",
    "for outcome in sample_space:\n",
    "    total += 1\n",
    "    if all(map(lambda x: x.rank == 'A', outcome)):\n",
    "        acceptable += 1\n",
    "\n",
    "print(f'total={total}, acceptable={acceptable}')\n",
    "print('odds={}'.format(Fraction(acceptable, total)))\n",
    "print('odds={:.10f}'.format(acceptable/total))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
